Valid Perfect Square
2020/5/9
概要
ある数字が与えられるので、その数が任意の整数のちょうど二乗であるか判定せよ、という問題
解法
最もオーソドックスな解き方だとおそらく二分探索で、これで解いた
2 ~ num / 2までの数を二分探索し、二乗した結果がnumになりうるかどうかで判定
関連
二分探索
code:binary-search.cpp
class Solution {
public:
bool isPerfectSquare(int num) {
if (num < 2) return true;
long long l = 2, r = num/2;
while (l <= r) {
long long p = l + (r-l)/2;
long long powed = pow(p, 2);
if (powed == num) return true;
if (powed < num) l = p+1;
else r = p-1;
}
return false;
}
};
ニュートン法
i = (i + num/i) / 2で常にiを更新しつつ探索していけばok
code:newton.cpp
class Solution {
public:
bool isPerfectSquare(int num) {
if (num < 2) return true;
long long i = num / 2;
while (pow(i, 2) > num) i = (i + num/i) / 2;
return (pow(i, 2) == num);
}
};